26. 基站最小覆盖半径[200分]

题目内容

网络规划团队正在为某一线型工业园区制定网络建设方案：园区内一条笔直道路贯穿其间，沿途分布着 n 个关键业务区域，其位置坐标由整数数组 positions 表示（数组成员严格递增）。

为了保证无缝漫游体验，方案要求相邻两个基站之间必须有足够的重叠覆盖区域，重叠区域长度至少为 minOverlap 米（即：相邻两个基站覆盖区间的交集长度至少为 minOverlap）。

团队手中有 m 个新型基站可用，为践行绿色节能理念，团队希望将基站的发射功率调整到最低（即覆盖半径最小）。

所有基站使用相同的覆盖半径 k，请计算在满足所有关键区域被覆盖、且相邻基站重叠满足要求的条件下，所需的最小信号覆盖半径 k（非负整数）。

数据范围：

• 关键区域位置数组 positions：-10^9 ≤ positions[i] ≤ 10^9，数组成员严格递增
• 最小重叠长度 minOverlap：0 ≤ minOverlap ≤ 10^9
• 可用基站数量 m：1 ≤ m ≤ 10^5

输入描述

输入共三行：

• 第一行：所有关键区域的位置 positions，以空格分隔
• 第二行：相邻基站最小重叠长度 minOverlap
• 第三行：可用基站数量 m

输出描述

输出一个整数，表示所需的最小信号覆盖半径 k。

样例

样例 1

输入

0 10 20
0
2

输出

5

说明：

• 关键区域间隔为 10，minOverlap = 0，m = 2，需要 2 个基站覆盖 3 个关键区域点。
• 第 1 个基站覆盖 0 和 10，中心点在 5，半径为 5，范围为 [0, 10]。
• 第 2 个基站覆盖 10 和 20，中心点在 15，半径为 5，范围为 [10, 20]。
• 两者在 10 处刚好相接，重叠长度为 0，满足条件。
• 半径小于 5 则无法连接中间的间隔。

代码

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let lines = [];
rl.on('line', (line) => {
    lines.push(line.trim());
});

rl.on('close', () => {
    // 第 1 行：所有关键区域的位置
    const positions = lines[0].split(/\s+/).map(Number);
    // 第 2 行：相邻基站最小重叠长度
    const minOverlap = Number(lines[1]);
    // 第 3 行：可用基站数量
    const m = Number(lines[2]);

    const n = positions.length;

    // ============================================================
    // 判断：如果每个基站半径都是 k，能不能用不超过 m 个基站覆盖所有点？
    // ============================================================
    function canCover(k) {
        let used = 0;   // 已经用了几个基站
        let i = 0;      // 当前待覆盖的关键点下标

        while (i < n) {
            // 为了让新基站覆盖 positions[i]，
            // 基站中心最远可以放在 positions[i] + k，
            // 此时它向右能覆盖到 positions[i] + 2k
            const right = positions[i] + 2 * k;

            used++;
            if (used > m) return false; // 基站不够，失败

            // 这个基站能覆盖从 positions[i] 开始的所有 <= right 的点
            i++;
            while (i < n && positions[i] <= right) {
                i++;
            }
        }

        return true; // 所有点都覆盖完了
    }

    function solve() {
        // 所有关键点中最左到最右的总长度
        const length = positions[n - 1] - positions[0];

        // ---------- 情况 1：不需要重叠 ----------
        // 直接二分最小的 k
        if (minOverlap === 0) {
            let left = 0;
            let right = length;

            while (left < right) {
                const mid = Math.floor((left + right) / 2);

                if (canCover(mid)) {
                    right = mid;       // mid 可行，尝试更小
                } else {
                    left = mid + 1;    // mid 不可行，必须更大
                }
            }

            return left;
        }

        // ---------- 情况 2：总长度不超过最小重叠 ----------
        // 说明一个基站就能覆盖所有点，
        // 半径至少是 length / 2，向上取整
        if (length <= minOverlap) {
            return Math.floor((length + 1) / 2);
        }

        // ---------- 情况 3：用公式直接算 ----------
        // m 个基站，每个半径 k，相邻重叠 minOverlap
        // 总覆盖长度 = 2mk - (m-1) * minOverlap
        // 要求 >= length
        // 所以 k >= (length + (m-1) * minOverlap) / (2m)
        // 向上取整即可
        const denominator = 2 * m;
        const numerator = length + (m - 1) * minOverlap;

        // 向上取整： (a + b - 1) / b 再向下取整
        return Math.floor((numerator + denominator - 1) / denominator);
    }

    console.log(solve());
});